package com.sunny.l20;

import java.util.ArrayList;
import java.util.HashMap;

public class Solution {

    private HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
    private HashMap<String, ArrayList<ArrayList<String>>> cache = new HashMap<>();

    public static void main(String[] args) {

        String s = "abcdc";
        ArrayList<ArrayList<String>> res = (new Solution()).partition(s);
        res.forEach(list->{
            list.forEach(str->{
                System.out.print(str+" ");
            });
            System.out.println();
        });

    }

    public ArrayList<ArrayList<String>> partition(String s) {
        pre(s);
        return dfs(s, 0);
    }

    public ArrayList<ArrayList<String>> dfs(String s, int ind){
        if(cache.containsKey(s)){
            return cache.get(s);
        }
        if("".equals(s)){
            ArrayList<String> tmp = new ArrayList<>();
            ArrayList<ArrayList<String>> ret = new ArrayList<>();
            ret.add(tmp);
            return ret;
        }
        ArrayList<ArrayList<String>> res = new ArrayList<>();
        for(int jInd: map.get(ind)){
            ArrayList<ArrayList<String>> tmpRes = dfs(s.substring(jInd-ind+1), jInd+1);
            for(ArrayList<String> ttRes: tmpRes){
                ArrayList<String> tttRes = new ArrayList<>();
                tttRes.add(s.substring(0, jInd-ind+1));
                tttRes.addAll(ttRes);
                res.add(tttRes);
            }
        }
        return res;
    }

    public void pre(String s){
        int len = s.length();
        for(int i=0;i<len;i++){
            for(int j=i;j<len;j++){
                if(judgePalindrome(s.substring(i, j+1))){
                    if(map.containsKey(i)){
                        map.get(i).add(j);
                    }else{
                        ArrayList<Integer> list = new ArrayList<>();
                        list.add(j);
                        map.put(i, list);
                    }
                }
            }
        }
    }

    public boolean judgePalindrome(String s){
        int i = 0;
        int j = s.length()-1;
        boolean flag = true;
        while (i < j){
            if(s.charAt(i) != s.charAt(j)){
                flag = false;
                break;
            }
            i++;
            j--;
        }
        return flag;
    }

}
